#include <cstdlib>
#include <memory.h>
#include <cstdio>

const int Max = 0x7fffffff;
const int N = 50;

int n;
int g[N][N], dis[N], visited[N];

int getMin() {
  int min = Max;
  int i;
  int pos;
  for (i = 2; i <= n; i++) {
    if (visited[i] == 0 && min > dis[i]) {
      min = dis[i];
      pos = i;
    }
  }
  return pos;
}

void update(int pos) {
  int i;

  visited[pos] = 1;

  for (i = 1; i <= n; i++) {
    if (visited[i] == 0 && dis[i] > g[i][pos]) {
      dis[i] = g[i][pos];
    }
  }
}

int prim() {
  visited[1] = 1;
  int i;
  int sum = 0;
  for (i = 2; i <= n; i++) {
    visited[i] = 0;
    dis[i] = g[i][1];
  }
  for (i = 1; i <= n - 1; i++) {
    int pos = getMin();
    printf("%d", pos);
    sum += dis[pos];
    update(pos);
  }

  return sum;
}

int main() {
  int i = 1, j = 1;
  int ans = 0;
  int w;
  //输入顶点数
  scanf("%d", &n);
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++) {
      if (i == j)
        g[i][j] = 0;
      else
        g[i][j] = Max;
    }
  //输入边的条数
  int edgenum;
  scanf("%d", &edgenum);
  int v1, v2;
  //请输入各条边依附的顶点及权值
  for (i = 1; i <= edgenum; i++) {
    scanf("%d%d%d", &v1, &v2, &w);
    g[v1][v2] = g[v2][v1] = w;
  }

//  for(int i = 0;i < n;i++){
//    for(int j = 0;j < n;j++){
//      printf("%d ",g[i][j]);
//    }
//    printf("\n");
//  }

  ans = prim();
  //权值
  printf("\n");
  printf("%d", ans);
//  system("pause");
  return 0;
}
